package com.Shuang.Demo6;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class MyLinkedList<E> {

    private int size;  //用于记录链表中节点个数

    //定义一个节点的内部类，作为链表的节点
    public static class Node<E> {
        E date;
        Node<E> next;

        public Node(E date, Node<E> next) {
            this.date = date;
            this.next = next;
        }
    }

    //添加节点方法，添加完成，返回头节点用于后续的遍历
    public Node<E> add(){

        //创建一个头节点
        Node<E> head = null;

        //创建节点添加数据
        Scanner sc = new Scanner(System.in);
        while (true){
            System.out.println("请您输入要添加节点的数据值：");
            E date = (E) sc.next();
            //输入exit添加所有数据完成跳出循环
            if (date.equals("exit")){
                break;
            }

            if (head == null){
                //说明是第一次添加节点
                head = new Node<E>(date, null);
                size++;
            }else {
                //头节点最后要返回，所以不动它，可以把头节点给到临时节点，让临时节点遍历到链表尾部添加节点(尾插法)
                Node<E> tempHead = head;
                while (tempHead.next != null){
                    tempHead = tempHead.next;
                }
                tempHead.next = new Node<E>(date, null);
                size++;
            }
        }
        return head;
    }

    //完成链表从 left 到 right两个位置的反转，反转后返回新的链表
    public Node<E> reverse(Node<E> head, int left, int right){
        //判断left right 合理性
        if (left < 1 || left > size || right < 1 || right > size || left >= right){
            return head;
        }

        //先把头节点存起来用于最后反转后链表的返回
        Node<E> newHead = head;

        //对整个链表进行遍历，再找 从left到right的节点数据都是什么，然后把这些数据放到新的集合里去，
        // 在新的集合倒着遍历拿到反转的数据再存到这个链表中去完成反转
        int index = 0;  //定义一个索引用于记录位置

        Node<E> markLeft = null;  /*定义一个标记节点，用于记录当index == left时
                                   保存下此时的节点，用于后面再把倒着遍历的数据从此时的节点往链表里存 */

        //定义一个集合用于存上述说到的数据
        List<E> dates = new ArrayList<>();

        while (head != null){
            index++;
            if (index == left){  //证明此时的位置就是数据反转的位置
                markLeft = head;  //记录此时的节点
            }

            //遍历从left到right的数据 存到新集合中
            if (index >= left && index <= right){
                E date = head.date;
                dates.add(date);
            }

            //说明此时已经将从左到右的数据存完了，直接跳出循环 提高性能
            if (index == right){
                break;
            }

            //头节点走到下一个位置
            head = head.next;
        }

        //开始倒着遍历新集合从markLeft位置往链表里存
        for (int i = dates.size() - 1; i >= 0; i--) {
            E date = dates.get(i);
            markLeft.date = date;
            markLeft = markLeft.next;
        }

        return newHead;
    }

    //接收头节点，对链表进行遍历输出
    public void forEach(Node<E> head){
        if (head == null){
            System.out.println(head);
            return;
        }

        while (head != null){
            System.out.print(head.date + " ");
            head = head.next;
        }
    }

}
